package com.example.demo.leetcode.zuocheng.heap;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/8/8 12:02
 */
public class Heap_大根堆 {

    // 大根堆排序

    /**
     * 思路
     *  在数组中表示一个二叉树: 当前节点i,  父节点 i-1/2  ,左右子节点 2*i+1, 2*i+2
     * (1)首先新建一个大根堆,每个插入的值跟父节点比较,大于 跟父节点交换
     * (2)建好后，取最大值移到最后一位，调整大根堆(小于最大的子节点，交换)。直到大根堆大小为1。堆排序结束
     */
    public static void heapSort(int[] arr) {

        int heapSize = arr.length;

        // 生成大根堆
        //  方法1: 从0开始循环遍历，
        //  每个节点尝试跟父节点比较(往前比较)，大于父节点，交换,大的往前移动
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }

        // 方法二: 从尾数开始向下沉
        //  从最后一个节点开始遍历，每个节点尝试和子节点比较，小于子节点，交换,小的往后移动
        // for(int j=arr.length-1;j>=0;j--){
        //     heapfiy(arr,j,heapSize);
        // }

        //arr 已经变成大根堆- 取第一个数到末尾进行下沉
        // [0,heapsize-1]排序, 把大的移动到第0位
        // 重复这个过程
        while (heapSize > 0) {
            swap(arr, 0, --heapSize);
            //way1: 最小值往下调整
            heapfiy(arr, 0, heapSize);
            //way2: 每个数往前移动
            //            for(int i =0;i<heapSize;i++){
            //                heapInsert(arr,i);
            //            }

        }
    }

    /**
     * 每个节点尝试跟父节点比较(往前比较)，大于父节点，交换,大的往前移动
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 从最后一个节点开始遍历，每个节点尝试和子节点比较，小于子节点，交换,小的往后移动
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapfiy(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int right = left + 1 < heapSize ? left + 1 : left;
            int largest = arr[left] > arr[right] ? left : right;
            if (arr[index] < arr[largest]) {
                swap(arr, index, largest);
                index = largest;
                left = index * 2 + 1;
            } else {
                break;
            }

        }
    }

    /**
     * 生成大根堆
     * @param arr
     */
    public static void buildHeap(int[] arr) {

        int heapSize = arr.length;

        // 生成大根堆
        //  方法1: 从0开始循环遍历，
        //  每个节点尝试跟父节点比较，大于父节点，交换
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
    }

    public static void buildHeap2(int[] arr) {
        int heapSize = arr.length;
        for(int j=arr.length-1;j>=0;j--){
            heapfiy(arr,j,heapSize);
        }
    }



    public static void swap(int[] arr, int son, int parent) {
        int temp = arr[son];
        arr[son] = arr[parent];
        arr[parent] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 6, 4, 7, 42, 1, 12, 22};

        buildHeap2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}
